This invention relates to the field of communication systems, and in particular to techniques for locating similar streams of packets in different communication channels.
The tracing of a message through a typical network is a difficult task, particularly when the message is partitioned into discrete smaller units, or packets, that are communicated independently, amongst thousands of other packets of other messages. The difficulty of this task is further compounded if the exact content of the message, or the exact content of each packet, is unknown. For ease of reference, the term packet is used herein in the general sense, to identify a transmission that is a subset of a series of transmissions, although the invention is not limited to packet-based protocols.
The complexity of the tracing task can be reduced by appropriately filtering the packets, using, for example, the identification of the source and/or destination node within the header of each packet, the time associated with each packet, and so on. In like manner, event-sequencing may be used to filter packets, wherein, for example, if the message is known to be in response to a request, messages originating before the time that the request is received can be ignored. However, even with such filtering techniques, the packets corresponding to the message to be traced are often intermixed among dozens or hundreds of packets of other messages.
In many trace scenarios, other characteristics of the target transaction are known, or able to be estimated, and the tracing task involves finding a sequence of packets that exhibit similar characteristics. In some instances, for example, the target message may be known to contain certain words or phrases, or may be known to consist of a certain sequence of identifiable packets, the packets being identifiable by particular content, by a size of the packet, and so on. These characteristics of the target message can be used to form a “reference” message, comprising a sequence of reference packets, and the trace task can be recast as the task of finding a sequence of packets within a traffic stream that best matches the sequence of reference packets.
It is an object of this invention to provide a system and method for finding a sequence of packets within a traffic stream that best matches a sequence of reference packets. It is a further object of this invention to provide this method and system for finding a matching sequence of packets based on characteristics associated with a target message. It is a further object of this invention to provide this method and system for finding a matching sequence of packets when an exact match between individual packets is not available.
These objects, and others, are achieved by a system and method that searches a traffic stream for a sequence of “matching” packets that exhibit a high degree of correlation or similarity to a sequence of “reference” packets. The correlation between matching and reference packets is based on a degree of correspondence between individual packets, as well as the sequence-order of the corresponding packets. A variation of the Needleman-Wunsch algorithm is preferably used to select corresponding packets in the traffic stream that provide a sequence-order that best matches the sequence-order of the reference packets, and the algorithm is further modified to reduce the required search-space for finding corresponding packets in the traffic stream.
The drawings are included for illustrative purposes and are not intended to limit the scope of the invention.